package Algorithm.Tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author cj
 * @Date 2022/5/22 17:01
 */
public class serial {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    // 先序
    public String serialByPre(Node head) {
        if (head == null) {
            return "#!";
        }
        String res = head.value + "!";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }

    public Node reconByPreString(String nodeStr) {
        String[] values = nodeStr.split("!");
        Queue<String> queue = new LinkedList<>();
        for (String  value : values) {
            queue.offer(value);
        }
        return reconPreOrder(queue);
    }

    public Node reconPreOrder(Queue<String> queue) {
        String value = queue.poll();
        if (value.equals("#")) {
            return null;
        }

        Node head = new Node(Integer.parseInt(value));
        head.left = reconPreOrder(queue);
        head.right = reconPreOrder(queue);
        return head;
    }

    // 层序
    public String serialByLevel(Node head) {
        if (head == null) {
            return "#!";
        }
        String res = head.value + "!";
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            if (head.left != null) {
                res += head.left.value + "!";
                queue.offer(head.left);
            } else {
                res += "#!";
            }
            if (head.right != null) {
                res += head.right.value + "!";
                queue.offer(head.right);
            } else {
                res += "#!";
            }
        }
        return res;
    }

    public Node reconByLevelString(String nodeStr) {
        String[] values = nodeStr.split("!");
        Queue<Node> queue = new LinkedList<>();
        int index = 0;
        Node head = generateNode(values[index++]);
        if (head != null) {
            queue.offer(head);
        }
        Node node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            node.left = generateNode(values[index++]);
            node.right = generateNode(values[index++]);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return head;
    }

    private Node generateNode(String value) {
        if (value.equals("#!")) {
            return null;
        }
        return new Node(Integer.valueOf(value));
    }

    public static void main(String[] args) {
        String a = "12!3!#!#!#!";
        serial serial = new serial();
        Node b = serial.reconByPreString(a);
        System.out.println(a);
    }
}
